#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
const ll N=2e5+10;
ll d[N];
ll u, v,n;
int main()
{
    cin >> n;
}